/* list of countries with numbers of neighbors */

countries(L,C) :- countriesbis(L,[],C).

countriesbis([],C,C).
countriesbis([next(X,Y)|L],C1,C4) :- addto(X,C1,C2),addto(Y,C2,C3),
				countriesbis(L,C3,C4).

addto(X,[],[[X,suc(0)]]).
addto(X,[[Y,N]|L],[[Y,suc(N)]|L]) :- metaeq(X,Y),!.
addto(X,[P|L1],[P|L2]) :- addto(X,L1,L2).

/* test if a goal has to wait */

waits(next(X,Y),[[Z,N]|C]) :- or(metaeq(X,Z),metaeq(Y,Z)),
				less(N,suc(suc(suc(suc(0))))).
waits(P,[U|C]) :- waits(P,C).

or(P,Q) :- P.
or(P,Q) :- Q.

less(0,suc(N)).
less(suc(N),suc(M)) :- less(N,M).

/* the map to be colored */

goals([R1,R2,R3,R4,R5,R6],[
next(R1,R2),
next(R1,R3),
next(R1,R5),
next(R1,R6),
next(R2,R3),
next(R2,R4),
next(R2,R5),
next(R2,R6),
next(R3,R4),
next(R3,R6),
next(R5,R6)]).

next(X,Y) :- color(X),color(Y),nott(egal(X,Y)).

egal(X,X).

color(y).
color(b).
color(g).
color(r).

nott(P) :- P, !, fail.
nott(←).

exd(mcc,colm).
metaeq(X,Y) :- nott(exd(X,Y)).

/* arranging the goals */

arrange(L1,S) :- countries(L1,C),split(L1,L2,L3,C),arrangebis(L3,L2,S).

arrangebis([],L,[L]) :- !.
arrangebis(L1,L2,[L1|S]) :- arrange(L2,S).

split([],[],[],C).
split([P|L1],L2,[P|L3],C) :- waits(P,C),!,split(L1,L2,L3,C).
split([P|L1],[P|L2],L3,C) :- split(L1,L2,L3,C).

/* main meta-program */

test :- goals(L1,L2),
write('countries'),ttynl,
write(L1),ttynl,ttynl,
write('unarranged goals'),ttynl,
write(L2),ttynl,ttynl,
write('arranged goals'),ttynl,
arrange(L2,S),write(S),ttynl,ttynl,
write('solution'),ttynl,
execute(S),write(L1),ttynl.

execute([]).
execute([L|S]) :- execute(S), executebis(L).

executebis([]).
executebis([P|L]) :- P,executebis(L).